The rapid evolution in the field of information processing, data communication, and multi-media office communication has led to the emergence of transmitting different classes of traffic via the same medium, such as offered on LANs (Local Area Network). The majority of existing networks, whether circuit-switched or packet-switched, are still oriented towards particular applications. Thus, we usually have different networks for voice, signalling, video and data applications operating in parallel and independently. While each of these networks is suitable for the application it is designed for, they are not very efficient for supporting other applications. The advantages of an integrated communication system which can accommodate a variety of diverse services with different bandwidth requirements has been recognized for some time. The following two articles "Design approaches and performance criteria for integrated voice/data switching", of M. J. Ross, Proc. IEEE, Vol. 65, September 1977, pp. 1283-1295, and "Plan today for tomorrow data/voice nets", of H. Frank, Data Communications, September 1978, pp. 51-62, relate already to the integration of different traffic classes. The objective of having a unified integrated network allowing the transmission of different traffic classes is the flexibility to cover existing as well as future services with good performance and economical resource utilization, and with a unified network management, operation and maintenance.
In the following sections, we describe the current approaches to integrate circuit-switched and packet-switched principles on LANs. With regard to the prevalent trend in the design of LANs and the unknown future traffic characteristics, we then formulate the objects for the self-adaptive transmission data structure and method of the present invention.
Already in the early seventies, publications dealt with the integration of circuit-switched and packet-switched principles on the same transmission medium. Publications started with an integration on point-to-point links, as described in the article of K. Kummerle, "Multiplexer Performance of Integrated Line- and Packet-Switched Traffic", 2nd Intern. Conf. on Computer Communications (ICCC), Stockholm, 1974, pp. 507-515. Afterwards the efforts were extended to LANs as well as High-Speed LANs (HSLANs), and switching nodes with an internal bus structure. Examples representative for the large number of publications relating to these efforts are:
D. Roffinella, C. Trinchero, G. Freschi, "Interworking Solutions for a Two-Level Integrated Services Local Area Network", IEEE J. on Sel. Areas in Comm., Vol. SAC-5, No. 9, 1987, pp. 1444-1453; PA0 J. H. M. Kleinen, "PHILAN: An Integrated Local Area Network for High Speed Applications", EFOC/LAN 86, Amsterdam, June 1986, pp. 83-87; PA0 R. Calvo, M. Teener, "FDDI-II Architectural and Implementation Examples", EFOC/LAN 90, Munich, June 1990, pp. 76-86. PA0 "Broadband Ring Communication System and Access Control Method", Application No.: 90810456.5, PA0 "Medium Access Technique for LAN Systems", Application No.: 91810224.5.
The current trend in the design of new LANs is to attach more users, to carry higher traffic rates, to achieve smaller delays, to integrate more services, and to cover larger geographical areas. To permit this wide variety of objectives, the evolving high-speed LANs must have concurrent access and slot reuse capability, must provide for frame-by-frame as well as cell-by-cell transmission, and must be able to handle circuit-switched services, too.
The suitable transmission data-structures are slotted to allow simultaneous medium access by geographically separated nodes. Because of this, LAN throughput does not degrade for increasing product of speed and distance. Destination removal (allowing slot reuse) has the high potential to increase system throughput significantly beyond the bit rate of the transmission medium. In today's LANs, transmission is via frames in contiguous slots. This avoids segmentation (thus, no labeling algorithm is necessary to identify segments), reduces transmission overhead, and receiver hardware becomes less complex and its buffer size can be kept smaller. Moreover, transmission by frames simplifies buffer management of multiple receiver buffers at high data rates significantly. At the other hand, transmission of ATM (Asynchronous Transfer Mode) cells is extensively promoted as solution for Broadband-Integrated Services Digital Network (B-ISDN). Moreover, for the foreseeable future, the demand for circuit-switched channels (video, PBX interconnection) on high-speed LANs becomes increasingly evident.
In slotted LANs, frames are guaranteed to be transmitted in contiguous slots either by pure reservation, as described in the publications of M. Nassehi, "CRMA: An Access Scheme for High-Speed LANs and MANs," IEEE International Conference on Communications, Atlanta, Ga., April 1990, pp. 1697-1702, and "Cyclic Reservation Multiple-Access Scheme for Gbit/s LANs and MANs based on Dual-Bus Configuration," Eighth European Fibre Optic and Local Area Networks Conference, EFOC/LAN, Munich, June 1990, pp. 246-251, or by using the buffer insertion technique as e.g. disclosed in the following European patent applications:
Recently, buffer insertion LANs have been augmented by providing a by-pass mechanism for the so-called synchronous slots, as for example described in the above named European patent applications 90810456.5 and 91810224.5. In this way, real-time response for time-sensitive connections is not affected by insertion buffer delays. This by-pass mechanism is a component of the described transmission data-structure. Additionally, fairness in insertion-buffer LANs is now manageable either by a credit mechanism, described in the European patent application 91810224.5, or by a reservation mechanism described in the European patent application 90810456.5.
Traffic types
In the following, we will denote circuit-switched channels by isochronous channels. Slots used for that purpose obey strict periodicity. Slots carrying traffic according to the packed-switched principle is differentiated in synchronous and asynchronous. Synchronous slots are used for time-sensitive connections like packetized voice and video or other real-time applications. These connections may need a play-out buffer to adjust network delay variations. All other traffic is transported by asynchronous slots. Essentially, the three traffic types differ in the variation of the end-to-end delay. Isochronous traffic exhibits a constant delay and thus its delay variation is zero. The delay variation for synchronous traffic varies within a limited range whereas that for asynchronous traffic can be considerably. In addition to these three traffic types, signalling traffic for network housekeeping functions (like monitoring, measurements, slot reservations, as disclosed in the European patent application 91810224.5, "Medium Access Technique for LAN Systems", congestion control, and in general network management) must be taken into consideration, too.
Requirement to adapt to continuously changing traffic characteristics
Most LANs are designed to perform at their best for a particular type of traffic, but become less efficient in an environment with strongly different traffic characteristics. As a very simple example, it has been shown that for long frames token rings perform considerably better than slotted rings (comparison without slot reuse), whereas for short messages this is reverse. Because of continuously changing traffic characteristics and the unknown mix of future traffic in B-ISDN, it is essential to have a transmission data-structure that naturally adapts to different and continuously changing traffic characteristics.
Conventional integration of circuit and packet switching on LANs
The integration of circuit switching (CS) and packet switching (PS) on the same medium of a LAN is based on a periodic framing period of constant length (e.g. 125 .mu.s). Framing organization may be partitioned (fixed boundary or movable boundary) with a slotted CS-region and an unstructured PS-region, or completely slotted with free allocation of CS-connections. In the latter approach, a PS-frame is either contiguously transmitted in the remaining slots or is transmitted by autonomous segments with address information (e.g. ATM cells). An extensive overview of these methods is described in the article of E.-H. Goldner, "An Integrated Circuit/Packet Switching Local Area Network--Performance Analysis and Comparison of Strategies", Computer Networks and ISDN Systems, Vol. 10, No. 3-4, October/November 1985, pp. 211-219.
A disadvantage of a framing period with a fixed boundary, where the bandwidth is separated in two fixed parts, is that the bandwidth cannot be shared when traffic demand changes dynamically. In systems using a framing period with a movable boundary, the size of the isochronous part is determined by the position of the last isochronous channel before the packet-switched part starts. Bandwidth of free isochronous channels lying before the last channel cannot be used without channel rearrangement. Channel rearrangement on a ring needs a considerable overhead in terms of organization and higher-layer communication to assure synchronization of all involved nodes as disclosed in the European patent 227852, "Local Area Communication System for Integrated Services Based on a Token-Ring Transmission Medium". Moving the boundary itself requires a similar overhead. Then, all nodes must be informed about the new position. On a ring, moving must be done in several steps to assure that no data is lost. First the nodes must be informed, then all nodes must confirm, and finally in a next round the new position of the CS/PS-boundary circuit-switched/packet-switched) becomes effective. Thus, also a considerable delay is involved.
In the other two approaches with a completely slotted framing period, slots for isochronous channels can be arbitrarily allocated. Slots have a flag indicating the traffic type, so that a frame can be transmitted in an interleaved manner between the isochronous channels. In the first approach, segments are variable and carry no addresses. In the second approach, segments are constant and have address information. Here, the segments or cells are autonomous, and thus parts of different frames can be transmitted interleaved, too. Bandwidth adapts optimally to traffic demand, but on a ring LAN establishment and release of isochronous channels encounter a similar problem as in the framing organization with a moveable boundary i.e. slots to be allocated for an isochronous channel must first be marked as reserved. Thereafter, they get allocated in the next roundtrip. Additionally, the nodes involved must be informed when the channel is available.
In FIG. 1, we highlight already the main difference between isochronous channel support via a movable boundary (left side of figure) and that via insert/remove self-adaption (right side) as is an integrated part of the inventive transmission data-structure. Initially, a framing period 1 exists with two isochronous channels CH1 and CH2. In the movable boundary approach, both channels are located at the begin of the framing period 10 (CS-region). The remaining part of the framing period 10 (PS-part) is used for asynchronous traffic. The first two positions of the framing period 10 are denoted by 11.1 through 11.5 and 12.1 through 12.5 to differentiate between the five considered time instants. Initially, locations 11.1 and 12.1 are used by isochronous channels CH1 and CH2, respectively. As CH1 terminates, location 11.2 becomes free but cannot be used by asynchronous traffic until CH2 is rearranged from location 12.3 to 11.3 and until boundary 13 is correspondingly moved. As mentioned before, these actions cause communication overhead and delayed usage of the freed bandwidth. When later on another isochronous channel has to be established, boundary 13 is moved so that location 12.4 becomes free. It must be noticed that the boundary 13 cannot be moved immediately, because it must be ensured that location 12.4 does not carry data. Finally, after some communication overhead, the new channel CH3 is available at the location 12.5. Compared with this mode of operation, the insert/remove self-adaptation approach to establish and release isochronous channels is extremely efficient. First, both channels can principally be located at arbitrarily positions. We denote the location of channel CH1 by 14.1 through 14.2, and that of channel CH2 by 15.1 through 15.3. Initially, two isochronous channels are located 14.1 and 15.1. All bandwidth around them is available for asynchronous traffic. When CH1 terminates, its bandwidth at location 14.2 becomes immediately available, i.e. without any delay and without communication overhead. In case that isochronous channel CH3 is to be allocated, it can be put anywhere in the framing period (here location 16.3). The key point here is that the channel is immediately available and needs (apart of course from the normal higher-layer set-up procedure) no extra communication overhead. This immediate allocation is possible by inserting the isochronous at the right location and by immediate or delayed removal of a corresponding number of asynchronous slots. Thus, generation of isochronous slots for the allocation of a new isochronous channel is accompanied by destroying free asynchronous slots whereby a temporary surplus of slots may occur when all asynchronous slot candidates are busy. At the other hand, releasing an isochronous channel causes a similar but opposite operation to be executed. This means, a now instantaneous removal of isochronous slots with simultaneous generation of asynchronous slots.
With respect to transmission robustness, the approaches with stricted slotted framing periods have the following drawback. Since only the begin of the framing period is used for synchronization, the recognition of individual slot boundaries relies only on counting. A synchronization loss can only be recovered at the begin of the next framing structure. During the elapsed time, secondary errors might be produced which require a complex recovery scheme to resolve them.
The nearest prior art for the present invention is given by the article of J. Y. Chao, W. T. Lee, L. Y. Kung, "A New Buffer Insertion Ring with Time Variant Priority Scheme to Facilitate Real-Time Image Transmission on a High Speed Integrated Local Area Network", 14th Conference on Local Computer Networks, Minneapolis, October, 1989, and the above named European patent application 90810456.5, "Broadband Ring Communication System and Access Control Method".
The objects of the inventive self-adaptive transmission method for slotted LANs, and the hardware implementation thereof, are given below.